Задача #M080D

Вам даются  m-штук n-мерных векторов. Также вам известны стоимости каждого вектора. Ваша задача выбрать n линейно независимых векторов с минимальной стоимостью. 

Линейно независимые векторы - это набор векторов, таких что ни один из них не может быть представлен в виде линейной комбинации остальных векторов в этом наборе. Формально, векторы \(v_1, v_2,…,v_n\)​ в линейном пространстве V называются линейно независимыми, если единственное решение уравнения

\(a_1 * v_1 + a_2 * v_2 + …. + a_n * v _n = 0\)

является когда \(a_1 = a_2 = a_3 = … a_n = 0\)

\(a_1, …, a_n\) - действительные числа

В первой строке даются два числа \(m\) и \(n\) \((3 <= n <= 50) (n <= m <= 2000)\)

Следующие \(m\) строк содержат вектор. Все координаты векторов являются целыми числами, по модулю не превышающими 2000.

Следующие \(m\) строк содержат числа \(c_i\), цена \(i\) - того вектора. Цены представляют собой положительные целые числа, не превышающие 15 000.
 

Если выбрать \(n\) линейно независимых векторов не получается вывести 0, иначе вывести минимальную сумму \(n\) линейно независимых векторов.